/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/binary-tree-serialization
@Language: C++
@Datetime: 16-02-09 05:43
*/

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    string serialize(TreeNode *root) {
        // write your code here
        queue<TreeNode*> q;
        string vs;
        if (root==NULL)
            return vs;
        q.push(root);
        char str[32];
        TreeNode *r;
        while(q.size()){
            r = q.front();
            if (r==NULL)
                vs.append("#,");
            else{
                q.push(r->left);
                q.push(r->right);
                sprintf(str,"%d,",r->val);
                vs.append(str);
            }
            q.pop();
        }
        return vs;
    }
    TreeNode *deserialize(string data) {
        // write your, code here
        if (data.length()<1)
            return NULL;
        for(int i=data.length()-1;i>=0;--i)
            if (data[i]==',')
                data[i] = ' ';
        stringstream istr(data);
        queue<TreeNode*> q;
        TreeNode *root=NULL,*r=NULL;
        char str[32];
        int val;
        istr>>val;
        root = new TreeNode(val);
        q.push(root);
        while(q.size()){
            r = q.front();
            q.pop();
            if(istr.eof())
                break;
            istr>>str;
            if (str[0]!='#'){
                sscanf(str,"%d",&val);
                r->left = new TreeNode(val);
                q.push(r->left);
            }
            istr>>str;
            if (str[0]!='#'){
                sscanf(str,"%d",&val);
                r->right = new TreeNode(val);
                q.push(r->right);
            }
        }
        return root;
    }
};
